home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / lalr.lha / lalr / lib / Parser.c < prev    next >
C/C++ Source or Header  |  1992-08-18  |  16KB  |  472 lines
  1. /* $Id: Parser.c,v 2.9 1992/08/07 15:28:42 grosch rel $ */
  2.  
  3. # define bool        char
  4. # define true        1
  5. # define false        0
  6.  
  7. $@ # include "@.h"
  8. # include "Errors.h"
  9.  
  10. # ifdef __cplusplus
  11. extern "C" {
  12. #    include "Memory.h"
  13. #    include "DynArray.h"
  14. #    include "Sets.h"
  15. #    ifndef BCOPY
  16. #       include <memory.h>
  17. #    endif
  18. }
  19. # else
  20. #    include "Memory.h"
  21. #    include "DynArray.h"
  22. #    include "Sets.h"
  23. #    ifndef BCOPY
  24. #       include <memory.h>
  25. #    endif
  26. # endif
  27.  
  28. # if defined __STDC__ | defined __cplusplus
  29. # define ARGS(parameters)    parameters
  30. # else
  31. # define ARGS(parameters)    ()
  32. # endif
  33.  
  34. # ifdef lex_interface
  35. $@ #    define $_GetToken    yylex
  36.      extern int yylex ();
  37. #    ifndef AttributeDef
  38. #    include "Positions.h"
  39. $@         typedef struct { tPosition Position; } $_tScanAttribute;
  40. $@         static    $_tScanAttribute    $_Attribute = {{ 0, 0 }};
  41. #    endif
  42. #    ifndef ErrorAttributeDef
  43. $@ #    define $_ErrorAttribute(Token, RepairAttribute)
  44. #    endif
  45. #    ifndef yyGetAttribute
  46. #    define yyGetAttribute(yyAttrStackPtr, Attribute) * yyAttrStackPtr = yylval
  47. #    endif
  48. # else
  49. $@ #    include "$.h"
  50. #    ifndef yyGetAttribute
  51. #    define yyGetAttribute(yyAttrStackPtr, Attribute) (yyAttrStackPtr)->Scan = Attribute
  52. #    endif
  53. # endif
  54.  
  55. $G    /* GLOBAL section is inserted here */
  56.  
  57. # if defined lex_interface & ! defined yylvalDef
  58.      tParsAttribute yylval;
  59. # endif
  60.  
  61. # ifndef yyInitStackSize
  62. #    define yyInitStackSize    100
  63. # endif
  64. # define yyNoState        0
  65.  
  66. $T    /* table constants are inserted here */
  67.  
  68. # define yyFirstFinalState    yyFirstReadTermState
  69.  
  70. typedef unsigned short    yyStateRange    ;
  71. typedef unsigned short    yySymbolRange    ;
  72. typedef struct    { yyStateRange Check, Next; } yyTCombType ;
  73.  
  74. $@     char *        @_TokenName    [yyLastTerminal + 1] = {
  75. $W    /* token names are inserted here */
  76. };
  77. static    yyTCombType    yyTComb        [yyTableMax + 1] = {
  78. $M
  79. };
  80. static    unsigned short    yyNComb        [yyNTableMax - yyLastTerminal] = {
  81. $N
  82. };
  83. static    yyTCombType *    yyTBasePtr    [yyLastReadState + 1] = {
  84. $P
  85. };
  86. static    unsigned short*    yyNBasePtr    [yyLastReadState + 1] = {
  87. $Q
  88. };
  89. static    unsigned short    yyDefault    [yyLastReadState + 1] = {
  90. $D
  91. };
  92. static    unsigned char    yyLength    [yyLastReduceState - yyFirstReduceState + 1] = {
  93. $K
  94. };
  95. static    yySymbolRange    yyLeftHandSide    [yyLastReduceState - yyFirstReduceState + 1] = {
  96. $H
  97. };
  98. static    yySymbolRange    yyContinuation    [yyLastReadState + 1] = {
  99. $O
  100. };
  101. static    unsigned short    yyFinalToProd    [yyLastReadNontermState - yyFirstReadTermState + 1] = {
  102. $F
  103. };
  104.  
  105. static    void    yyErrorRecovery        ARGS((yySymbolRange * yyTerminal, yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr));
  106. static    void    yyComputeContinuation    ARGS((yyStateRange * yyStack, unsigned long yyStackSize, short yyStackPtr, tSet * yyContinueSet));
  107. static    bool    yyIsContinuation    ARGS((yySymbolRange yyTerminal, yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr));
  108. static    void    yyComputeRestartPoints    ARGS((yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr, tSet * yyRestartSet));
  109. static    yyStateRange yyNext        ARGS((yyStateRange yyState, yySymbolRange yySymbol));
  110. $@ static    void    Begin@        ();
  111.  
  112. $@ int @ ()
  113.    {
  114.       register    yyStateRange    yyState        ;
  115.       register    long        yyTerminal    ;
  116.       register    yyStateRange *    yyStateStackPtr ;
  117.       register    tParsAttribute *yyAttrStackPtr    ;
  118.       register    bool        yyIsRepairing    ;
  119.         unsigned long    yyStateStackSize= yyInitStackSize;
  120.         unsigned long    yyAttrStackSize = yyInitStackSize;
  121.         yyStateRange *    yyStateStack    ;
  122.         tParsAttribute* yyAttributeStack;
  123.         tParsAttribute    yySynAttribute    ;    /* synthesized attribute */
  124.       register    yyStateRange *    yyEndOfStack    ;
  125.         int        yyErrorCount    = 0;
  126.    
  127. $L    /* LOCAL section is inserted here */
  128.  
  129. $@       Begin@ ();
  130.       yyState        = yyStartState;
  131. $@       yyTerminal    = $_GetToken ();
  132.       MakeArray ((char * *) & yyStateStack, & yyStateStackSize, sizeof (yyStateRange));
  133.       MakeArray ((char * *) & yyAttributeStack, & yyAttrStackSize, sizeof (tParsAttribute));
  134.       yyEndOfStack    = & yyStateStack [yyStateStackSize];
  135.       yyStateStackPtr    = yyStateStack;
  136.       yyAttrStackPtr    = yyAttributeStack;
  137.       yyIsRepairing    = false;
  138.  
  139.    ParseLoop:
  140.       for (;;) {
  141.      if (yyStateStackPtr >= yyEndOfStack) {
  142.         int yyyStateStackPtr= yyStateStackPtr - yyStateStack;
  143.         int yyyAttrStackPtr    = yyAttrStackPtr - yyAttributeStack;
  144.         ExtendArray ((char * *) & yyStateStack, & yyStateStackSize, sizeof (yyStateRange));
  145.         ExtendArray ((char * *) & yyAttributeStack, & yyAttrStackSize, sizeof (tParsAttribute));
  146.         yyStateStackPtr    = yyStateStack + yyyStateStackPtr;
  147.         yyAttrStackPtr    = yyAttributeStack + yyyAttrStackPtr;
  148.         yyEndOfStack    = & yyStateStack [yyStateStackSize];
  149.      }
  150.      * yyStateStackPtr = yyState;
  151.  
  152.    TermTrans:
  153.      for (;;) {    /* SPEC State = Next (State, Terminal); terminal transition */
  154.         register short * yyTCombPtr;
  155.  
  156.         yyTCombPtr = (short *) (yyTBasePtr [yyState] + yyTerminal);
  157.         if (* yyTCombPtr ++ == yyState) { yyState = * yyTCombPtr; break; }
  158.         if ((yyState = yyDefault [yyState]) != yyNoState) goto TermTrans;
  159.  
  160.                             /* syntax error */
  161.         if (! yyIsRepairing) {            /* report and recover */
  162.            yySymbolRange yyyTerminal = yyTerminal;
  163.  
  164.            yyErrorCount ++;
  165.            yyErrorRecovery (& yyyTerminal, yyStateStack, yyStateStackSize, yyStateStackPtr - yyStateStack);
  166.            yyTerminal = yyyTerminal;
  167.            yyIsRepairing = true;
  168.         }
  169.         yyState = * yyStateStackPtr;
  170.         for (;;) {
  171.            if (yyNext (yyState, (yySymbolRange) yyTerminal) == yyNoState) { /* repair */
  172.           yySymbolRange        yyRepairToken;
  173. $@           $_tScanAttribute    yyRepairAttribute;
  174.         
  175.           yyRepairToken = yyContinuation [yyState];
  176.           yyState = yyNext (yyState, yyRepairToken);
  177.           if (yyState <= yyLastReadTermState) { /* read or read terminal reduce ? */
  178. $@              $_ErrorAttribute ((int) yyRepairToken, & yyRepairAttribute);
  179. $@              ErrorMessageI (xxTokenInserted, xxRepair, $_Attribute.Position,
  180. $@             xxString, @_TokenName [yyRepairToken]);
  181.              if (yyState >= yyFirstFinalState) {    /* avoid second push */
  182.             yyState = yyFinalToProd [yyState - yyFirstReadTermState];
  183.              }
  184.              yyGetAttribute (yyAttrStackPtr ++, yyRepairAttribute);
  185.              * ++ yyStateStackPtr = yyState;
  186.           }
  187.           if (yyState >= yyFirstFinalState) goto Final; /* final state ? */
  188.            } else {
  189.           yyState = yyNext (yyState, (yySymbolRange) yyTerminal);
  190.           goto Final;
  191.            }
  192.         }
  193.      }
  194.  
  195.    Final:
  196.      if (yyState >= yyFirstFinalState) {        /* final state ? */
  197.         if (yyState <= yyLastReadTermState) {    /* read terminal reduce ? */
  198.            yyStateStackPtr ++;
  199. $@            yyGetAttribute (yyAttrStackPtr ++, $_Attribute);
  200. $@            yyTerminal = $_GetToken ();
  201.            yyIsRepairing = false;
  202. $X           yyState = yyFinalToProd [yyState - yyFirstReadTermState];
  203.         }
  204.  
  205.         for (;;) {
  206.            /* register long yyNonterminal;        /* left-hand side */
  207. # define yyNonterminal yyState
  208.  
  209. $R    /* Code for Reductions is inserted here */
  210.  
  211.            /* SPEC State = Next (Top (), Nonterminal); nonterminal transition */
  212.            yyState = * (yyNBasePtr [* yyStateStackPtr ++] + yyNonterminal);
  213.            * yyAttrStackPtr ++ = yySynAttribute;
  214.            if (yyState < yyFirstFinalState) goto ParseLoop; /* read nonterminal reduce ? */
  215. $X           yyState = yyFinalToProd [yyState - yyFirstReadTermState];
  216.         } 
  217.  
  218.      } else {                    /* read */
  219.         yyStateStackPtr ++;
  220. $@         yyGetAttribute (yyAttrStackPtr ++, $_Attribute);
  221. $@         yyTerminal = $_GetToken ();
  222.         yyIsRepairing = false;
  223.      }
  224.       }
  225.    }
  226.  
  227. static void yyErrorRecovery
  228. # if defined __STDC__ | defined __cplusplus
  229.    (yySymbolRange * yyTerminal, yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr)
  230. # else
  231.    (yyTerminal, yyStateStack, yyStackSize, yyStackPtr)
  232.    yySymbolRange *    yyTerminal    ;
  233.    yyStateRange *    yyStateStack    ;
  234.    unsigned long    yyStackSize    ;
  235.    short        yyStackPtr    ;
  236. # endif
  237.    {
  238.       bool    yyTokensSkipped    ;
  239.       tSet    yyContinueSet    ;
  240.       tSet    yyRestartSet    ;
  241.       int    yyLength = 0    ;
  242.       char    yyContinueString [256];
  243.  
  244.    /* 1. report an error */
  245. $@       ErrorMessage (xxSyntaxError, xxError, $_Attribute.Position);
  246.  
  247.    /* 2. report the set of expected terminal symbols */
  248.       MakeSet (& yyContinueSet, (short) yyLastTerminal);
  249.       yyComputeContinuation (yyStateStack, yyStackSize, yyStackPtr, & yyContinueSet);
  250.       yyContinueString [0] = '\0';
  251.       while (! IsEmpty (& yyContinueSet)) {
  252. $@      char * yyTokenString = @_TokenName [Extract (& yyContinueSet)];
  253.      if ((yyLength += strlen (yyTokenString) + 1) >= 256) break;
  254.      (void) strcat (yyContinueString, yyTokenString);
  255.      (void) strcat (yyContinueString, " ");
  256.       }
  257. $@       ErrorMessageI (xxExpectedTokens, xxInformation, $_Attribute.Position,
  258.      xxString, yyContinueString);
  259.       ReleaseSet (& yyContinueSet);
  260.  
  261.    /* 3. compute the set of terminal symbols for restart of the parse */
  262.       MakeSet (& yyRestartSet, (short) yyLastTerminal);
  263.       yyComputeRestartPoints (yyStateStack, yyStackSize, yyStackPtr, & yyRestartSet);
  264.  
  265.    /* 4. skip terminal symbols until a restart point is reached */
  266.       yyTokensSkipped = false;
  267.       while (! IsElement (* yyTerminal, & yyRestartSet)) {
  268. $@      * yyTerminal = $_GetToken ();
  269.      yyTokensSkipped = true;
  270.       }
  271.       ReleaseSet (& yyRestartSet);
  272.  
  273.    /* 5. report the restart point */
  274.       if (yyTokensSkipped) {
  275. $@      ErrorMessage (xxRestartPoint, xxInformation, $_Attribute.Position);
  276.       }
  277.    }
  278.  
  279. /*
  280.    compute the set of terminal symbols that can be accepted (read)
  281.    in a given stack configuration (eventually after reduce actions)
  282. */
  283.  
  284. static void yyComputeContinuation
  285. # if defined __STDC__ | defined __cplusplus
  286.    (yyStateRange * yyStack, unsigned long yyStackSize, short yyStackPtr, tSet * yyContinueSet)
  287. # else
  288.    (yyStack, yyStackSize, yyStackPtr, yyContinueSet)
  289.    yyStateRange *    yyStack        ;
  290.    unsigned long    yyStackSize    ;
  291.    short        yyStackPtr    ;
  292.    tSet *        yyContinueSet    ;
  293. # endif
  294.    {
  295.       register yySymbolRange    yyTerminal;
  296.       register yyStateRange    yyState = yyStack [yyStackPtr];
  297.  
  298.       AssignEmpty (yyContinueSet);
  299.       for (yyTerminal = yyFirstTerminal; yyTerminal <= yyLastTerminal; yyTerminal ++) {
  300.      if (yyNext (yyState, yyTerminal) != yyNoState &&
  301.         yyIsContinuation (yyTerminal, yyStack, yyStackSize, yyStackPtr)) {
  302.         Include (yyContinueSet, (short) yyTerminal);
  303.      }
  304.       }
  305.    }
  306.  
  307. /*
  308.    check whether a given terminal symbol can be accepted (read)
  309.    in a certain stack configuration (eventually after reduce actions)
  310. */
  311.  
  312. static bool yyIsContinuation
  313. # if defined __STDC__ | defined __cplusplus
  314.    (yySymbolRange yyTerminal, yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr)
  315. # else
  316.    (yyTerminal, yyStateStack, yyStackSize, yyStackPtr)
  317.    yySymbolRange    yyTerminal    ;
  318.    yyStateRange *    yyStateStack    ;
  319.    unsigned long    yyStackSize    ;
  320.    short        yyStackPtr    ;
  321. # endif
  322.    {
  323.       register yyStateRange    yState        ;
  324.       register yySymbolRange    yyNonterminal    ;
  325.            yyStateRange *    yyStack        ;
  326.    
  327.       MakeArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));    /* pass Stack by value */
  328. # ifdef BCOPY
  329.       bcopy ((char *) yyStateStack, (char *) yyStack, (int) sizeof (yyStateRange) * (yyStackPtr + 1));
  330. # else
  331.       (void) memcpy ((char *) yyStack, (char *) yyStateStack, (int) sizeof (yyStateRange) * (yyStackPtr + 1));
  332. # endif
  333.  
  334.       yState = yyStack [yyStackPtr];
  335.       for (;;) {
  336.      yyStack [yyStackPtr] = yState;
  337.      yState = yyNext (yState, yyTerminal);
  338.      if (yState == yyNoState) {
  339.         ReleaseArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));
  340.         return false;
  341.      }
  342.      if (yState <= yyLastReadTermState) {        /* read or read terminal reduce ? */
  343.         ReleaseArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));
  344.         return true;
  345.      }
  346.  
  347.      for (;;) {                    /* reduce */
  348.         if (yState == yyStopState) {
  349.            ReleaseArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));
  350.            return true;
  351.         } else { 
  352.            yyStackPtr -= yyLength [yState - yyFirstReduceState];
  353.            yyNonterminal = yyLeftHandSide [yState - yyFirstReduceState];
  354.         }
  355.  
  356.         yState = yyNext (yyStack [yyStackPtr], yyNonterminal);
  357.         if (yyStackPtr >= yyStackSize) {
  358.            ExtendArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));
  359.         }
  360.         yyStackPtr ++;
  361.         if (yState < yyFirstFinalState) break;    /* read nonterminal ? */
  362.         yState = yyFinalToProd [yState - yyFirstReadTermState];    /* read nonterminal reduce */
  363.      }
  364.       }
  365.    }
  366.  
  367. /*
  368.    compute a set of terminal symbols that can be used to restart
  369.    parsing in a given stack configuration. we simulate parsing until
  370.    end of file using a suffix program synthesized by the function
  371.    Continuation. All symbols acceptable in the states reached during
  372.    the simulation can be used to restart parsing.
  373. */
  374.  
  375. static void yyComputeRestartPoints
  376. # if defined __STDC__ | defined __cplusplus
  377.    (yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr, tSet * yyRestartSet)
  378. # else
  379.    (yyStateStack, yyStackSize, yyStackPtr, yyRestartSet)
  380.    yyStateRange *    yyStateStack    ;
  381.    unsigned long    yyStackSize    ;
  382.    short        yyStackPtr    ;
  383.    tSet *        yyRestartSet    ;
  384. # endif
  385.    {
  386.       register yyStateRange    yState        ;
  387.       register yySymbolRange    yyNonterminal    ;
  388.            yyStateRange *    yyStack        ;
  389.            tSet        yyContinueSet    ;
  390.    
  391.       MakeArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange)); /* pass Stack by value */
  392. # ifdef BCOPY
  393.       bcopy ((char *) yyStateStack, (char *) yyStack, (int) sizeof (yyStateRange) * (yyStackPtr + 1));
  394. # else
  395.       (void) memcpy ((char *) yyStack, (char *) yyStateStack, (int) sizeof (yyStateRange) * (yyStackPtr + 1));
  396. # endif
  397.  
  398.       MakeSet (& yyContinueSet, (short) yyLastTerminal);
  399.       AssignEmpty (yyRestartSet);
  400.       yState = yyStack [yyStackPtr];
  401.  
  402.       for (;;) {
  403.      if (yyStackPtr >= yyStackSize) {
  404.         ExtendArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));
  405.      }
  406.      yyStack [yyStackPtr] = yState;
  407.      yyComputeContinuation (yyStack, yyStackSize, yyStackPtr, & yyContinueSet);
  408.      Union (yyRestartSet, & yyContinueSet);
  409.      yState = yyNext (yState, yyContinuation [yState]);
  410.  
  411.      if (yState >= yyFirstFinalState) {        /* final state ? */
  412.         if (yState <= yyLastReadTermState) {    /* read terminal reduce ? */
  413.            yyStackPtr ++;
  414.            yState = yyFinalToProd [yState - yyFirstReadTermState];
  415.         }
  416.  
  417.         for (;;) {                    /* reduce */
  418.            if (yState == yyStopState) {
  419.           ReleaseSet (& yyContinueSet);
  420.           ReleaseArray ((char * *) & yyStack, & yyStackSize, sizeof (yyStateRange));
  421.           return;
  422.            } else { 
  423.           yyStackPtr -= yyLength [yState - yyFirstReduceState];
  424.           yyNonterminal = yyLeftHandSide [yState - yyFirstReduceState];
  425.            }
  426.  
  427.            yState = yyNext (yyStack [yyStackPtr], yyNonterminal);
  428.            yyStackPtr ++;
  429.            if (yState < yyFirstFinalState) break;    /* read nonterminal ? */
  430.            yState = yyFinalToProd [yState - yyFirstReadTermState]; /* read nonterminal reduce */
  431.         }
  432.      } else {                    /* read */
  433.         yyStackPtr ++;
  434.      }
  435.       }
  436.    }
  437.  
  438. /* access the parse table:   Next : State x Symbol -> Action */
  439.  
  440. static yyStateRange yyNext
  441. # if defined __STDC__ | defined __cplusplus
  442.    (yyStateRange yyState, yySymbolRange yySymbol)
  443. # else
  444.    (yyState, yySymbol) yyStateRange yyState; yySymbolRange yySymbol;
  445. # endif
  446.    {
  447.       register yyTCombType * yyTCombPtr;
  448.  
  449.       if (yySymbol <= yyLastTerminal) {
  450.      for (;;) {
  451.         yyTCombPtr = yyTBasePtr [yyState] + yySymbol;
  452.         if (yyTCombPtr->Check != yyState) {
  453.            if ((yyState = yyDefault [yyState]) == yyNoState) return yyNoState;
  454.         } else {
  455.            return yyTCombPtr->Next;
  456.         }
  457.      }
  458.       } else {
  459.     return * (yyNBasePtr [yyState] + yySymbol);
  460.       }
  461.    }
  462.  
  463. $@ static void Begin@ ()
  464.    {
  465. $B    /* BEGIN section is inserted here */
  466.    }
  467.  
  468. $@ void Close@ ()
  469.    {
  470. $C    /* CLOSE section is inserted here */
  471.    }
  472.